/*
https://leetcode-cn.com/problems/ugly-number-ii/solution/chou-shu-ii-by-leetcode-solution-uoqd/
 */
public class Solution264 {
    public int nthUglyNumber(int n) {
        int[] f=new int[n];
        f[0]=1;
        int p1=0,p2=0,p3=0;
        for (int i=1;i<n;i++){
            f[i]=Math.min(Math.min(f[p1]*2,f[p2]*3),f[p3]*5);
            if (f[i]==f[p1]*2){
                p1++;
            }
            if (f[i]==f[p2]*3){
                p2++;
            }
            if (f[i]==f[p3]*5){
                p3++;
            }
        }
        return f[n-1];
    }

    public static void main(String[] args) {
        System.out.println(new Solution264().nthUglyNumber(10));
    }
}
